{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "0187cfb0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Original Message: 123\n",
      "Encrypted Message: 124872\n",
      "Decrypted Message: 123\n",
      "Public key: (141727, 52447)\n",
      "Private key: (141727, 19423)\n"
     ]
    }
   ],
   "source": [
    "import random\n",
    "\n",
    "def is_prime(num):\n",
    "    if num < 2:\n",
    "        return False\n",
    "    for i in range(2, int(num**0.5) + 1):\n",
    "        if num % i == 0:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def gcd(a, b):\n",
    "    while b:\n",
    "        a, b = b, a % b\n",
    "    return a\n",
    "\n",
    "def modinv(a, b):\n",
    "    m0, x0, x1 = b, 0, 1\n",
    "    while a > 1:\n",
    "        q = a // b\n",
    "        a, b = b, a % b\n",
    "        x0, x1 = x1 - q * x0, x0\n",
    "    return x1 + m0 if x1 < 0 else x1\n",
    "\n",
    "def generate_keypair():\n",
    "    p, q = random_prime(), random_prime()\n",
    "    n = p * q\n",
    "    phi = (p - 1) * (q - 1)\n",
    "    e = random.randint(2, phi - 1)\n",
    "    while gcd(e, phi) != 1:\n",
    "        e = random.randint(2, phi - 1)\n",
    "    d = modinv(e, phi)\n",
    "    return ((n, e), (n, d))\n",
    "\n",
    "def random_prime():\n",
    "    while True:\n",
    "        num = random.randint(10**2, 10**3)\n",
    "        if is_prime(num):\n",
    "            return num\n",
    "\n",
    "def encrypt(message, public_key):\n",
    "    n, e = public_key\n",
    "    return pow(int(message), e, n)\n",
    "\n",
    "def decrypt(ciphertext, private_key):\n",
    "    n, d = private_key\n",
    "    return pow(ciphertext, d, n)\n",
    "\n",
    "# 示例\n",
    "message = 123\n",
    "public_key, private_key = generate_keypair()\n",
    "encrypted_message = encrypt(message, public_key)\n",
    "decrypted_message = decrypt(encrypted_message, private_key)\n",
    "\n",
    "print(\"Original Message:\", message)\n",
    "print(\"Encrypted Message:\", encrypted_message)\n",
    "print(\"Decrypted Message:\", decrypted_message)\n",
    "print(\"Public key:\", public_key)\n",
    "print(\"Private key:\", private_key)\n",
    "\n",
    "## Example Output:\n",
    "# Original Message: 123\n",
    "# Encrypted Message: 124872\n",
    "# Decrypted Message: 123\n",
    "# Public key: (141727, 52447)\n",
    "# Private key: (141727, 19423)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8e578d36",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
